<?php
/**
 * 单链表
 * 没有虚拟头结点
 */

namespace Xxb\XxbPhpAlgo;

use Xxb\XxbPhpAlgo\Contract\XxbLinkedListInterface;

class SingleLinkedList implements XxbLinkedListInterface
{
    /**
     * 记录结点个数
     * @var int
     */
    private $size;

    /**
     * @return int
     */
    public function getSize(): int
    {
        return $this->size;
    }

    /**
     * @var null|SingleLinkedListNode
     */
    private $head;

    /**
     * @return SingleLinkedListNode|null
     */
    public function getHead()
    {
        return $this->head;
    }

    /**
     * @param SingleLinkedListNode|null $head
     */
    public function setHead($head)
    {
        $this->head = $head;
    }

    public function __construct()
    {
        $this->size = 0;
        $this->setHead(null);
    }

    /**
     * @return bool
     */
    public function isEmpty()
    {
        return $this->size == 0;
    }

    /**
     * @return int
     */
    public function count()
    {
        return $this->size;
    }

    /**
     * 指定位置添加结点：
     * 1. 往头（index=0）添加
     * 2. 往头部之外（index>0 and index<=size）添加
     * @param $index
     * @param $value
     */
    public function add($index, $value)
    {
        if ($index < 0 || $index > $this->size) {
            throw new \RuntimeException('invalid index. index must be egt 0 and elt size.');
        }

        if ($index === 0) {
            $this->head = new SingleLinkedListNode($value, $this->head);
        } else {
            // 找到index-1位置
            for ($i=1, $cursor = $this->head; $i<$index; $i++) {
                $cursor = $cursor->getNext();
            }
            $node = new SingleLinkedListNode($value, $cursor->getNext());
            $cursor->setNext($node);
        }
        $this->size++;
    }

    public function unshift($value)
    {
        $this->add(0, $value);
    }

    public function push($value)
    {
        $this->add($this->size, $value);
    }

    /**
     * @param $index
     *
     * @return mixed|null
     */
    public function offsetUnset($index)
    {
        if ($this->isEmpty()) {
            throw new \RuntimeException('remove error, empty linked list!');
        }
        if ($index < 0 || $index >= $this->size) {
            throw new \RuntimeException('remove error, illegal index!');
        }
        $result = null;
        if ($index == 0) {
            // 删除表头结点
            $result = $this->head->value;
            $this->head = $this->head->next;
        } else {
            // 删除表中间、表尾的结点
            for ($i=0, $cursor = $this->head; $i<$index-1; $i++) {
                $cursor = $cursor->next;
            }
            $result = $cursor->next->value;
            $cursor->next = $cursor->next->next;
        }
        $this->size--;
        return $result;
    }

    /**
     * @return mixed|null
     */
    public function pop()
    {
        return $this->offsetUnset($this->size - 1);
    }

    /**
     * @return mixed|null
     */
    public function shift()
    {
        return $this->offsetUnset(0);
    }

    /**
     * 正向遍历，删除第一次出现该值的结点
     * 有就删除
     *
     * @param $value
     */
    public function unsetVal($value)
    {
        $cursor = $this->head;
        $preNode = null; // 被删除结点的上一个结点
        while (!empty($cursor)) {
            if ($cursor->value == $value) {
                if ($cursor == $this->head) {
                    // 删除值正好在表头
                    $this->head = $this->head->next;
                } else {
                    // 删除值在表中间或者表尾
                    $preNode->next = $cursor->next;
                }
                $cursor = null;
                $this->size--;
                break;
            }
            $preNode = $cursor;
            $cursor = $cursor->next;
        }
    }

    public function offsetSet($index, $value)
    {
        if ($this->isEmpty()) {
            throw new \RuntimeException('set value error, empty linked list!');
        }
        if ($index < 0 || $index >= $this->size) {
            throw new \RuntimeException('set value error, illegal index!');
        }
        for ($i=0, $cursor=$this->head; $i<$index; $i++) {
            $cursor = $cursor->next;
        }
        $cursor->value = $value;
    }

    public function valueOffsetGet($value)
    {
        for ($i=0, $cursor=$this->head; $i<$this->size; $i++) {
            if ($cursor->value == $value) {
                return $i;
            }
            $cursor = $cursor->next;
        }
        return -1;
    }

    public function valueExists($value)
    {
        return $this->valueOffsetGet($value) != -1;
    }

    public function offsetGet($index)
    {
        if ($index < 0 || $index >= $this->size) {
            throw new \RuntimeException('get error, illegal index!');
        }
        for ($i=0, $cursor=$this->head; $i<$index; $i++) {
            $cursor = $cursor->next;
        }
        return $cursor->value;
    }

    public function bottom()
    {
        return $this->offsetGet(0);
    }

    public function top()
    {
        return $this->offsetGet($this->size - 1);
    }

    /**
     * 对象字符串化
     * @return string
     */
    public function __toString()
    {
        $str = 'link list: top [';
        for ($i=1, $cursor = $this->head, $str .= $cursor->getValue(); $i<$this->size; $i++) {
            $cursor = $cursor->getNext();
            $str .= '->' . $cursor->getValue();
        }
        $str .= ']';
        return $str;
    }
}
